package xyz.scootaloo.adt.tree.bst;

import xyz.scootaloo.adt.tree.BNode;

/**
 * 普通的二叉查找树
 *
 * @author flutterdash@qq.com
 * @since 2021/3/11 10:30
 */
public class BSTree<T extends Comparable<T>> {

    private BNode<T> root;
    private int size;

    public BSTree() {
        size = 0;
    }

    public boolean insert(T value) {
        if (root == null) {
            root = new BNode<>(value);
            size++;
            return true;
        }
        BNode<T> targetNode = new BNode<>(value);
        return insert(root, targetNode);
    }

    public T remove(T value) {
        if (root == null)
            return null;
        BNode<T> targetNode = findNode(root, value);
        if (targetNode == null)
            return null;

        return null;
    }

    public boolean update(T oldValue, T newValue) {
        BNode<T> targetNode = findNode(root, oldValue);
        if (targetNode != null) {
            targetNode.setKey(newValue);
            return true;
        }
        return false;
    }

    public boolean containsKey(T value) {
        if (root == null)
            return false;
        return findNode(root, value) != null;
    }

    private boolean insert(BNode<T> currentNode, BNode<T> targetNode) {
        int diff = currentNode.getKey().compareTo(targetNode.getKey());
        // 无需插入，此键已经存在
        if (diff == 0)
            return false;
        // 当前节点大于目标节点，向左遍历
        if (diff > 0) {
            if (currentNode.getLeftChild() == null) {
                currentNode.setLeftChild(targetNode);
                size++;
                return true;
            } else {
                return insert(currentNode.getLeftChild(), targetNode);
            }
        }
        // 当前节点小于目标节点，向右遍历
        else {
            if (currentNode.getRightChild() == null) {
                currentNode.setRightChild(targetNode);
                size++;
                return true;
            } else {
                return insert(currentNode.getRightChild(), targetNode);
            }
        }
    }

    private BNode<T> findNode(BNode<T> currentNode, T key) {
        if (currentNode.getKey().equals(key))
            return currentNode;
        int diff = currentNode.getKey().compareTo(key);
        if (diff > 0) {
            if (currentNode.getLeftChild() == null)
                return null;
            return findNode(currentNode.getLeftChild(), key);
        } else {
            if (currentNode.getRightChild() == null)
                return null;
            return findNode(currentNode.getRightChild(), key);
        }
    }

}
